from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        使用回溯算法生成所有子集
        :param nums: 输入数组
        :return: 所有可能的子集
        """
        result = []
        current_subset = []
        
        def backtrack(start_index):
            # 将当前子集添加到结果中（需要复制，避免引用问题）
            result.append(current_subset[:])
            
            # 从start_index开始遍历，避免重复
            for i in range(start_index, len(nums)):
                # 选择当前元素
                current_subset.append(nums[i])
                # 递归处理剩余元素
                backtrack(i + 1)
                # 撤销选择（回溯）
                current_subset.pop()
        
        backtrack(0)
        return result
    
    def subsets_iterative(self, nums: List[int]) -> List[List[int]]:
        """
        迭代方法实现子集生成（位掩码方法）
        :param nums: 输入数组
        :return: 所有可能的子集
        """
        n = len(nums)
        result = []
        
        # 总共有2^n个子集
        for mask in range(1 << n):
            subset = []
            for i in range(n):
                # 检查第i位是否为1
                if mask & (1 << i):
                    subset.append(nums[i])
            result.append(subset)
        
        return result
